#include<iostream>
using namespace std;
class MyLinkedList {
private:
	struct Node {
		int val;
		Node* next;
		Node(int x) : val(x), next(nullptr) {}
	};
	Node* dummyHead;
	int size;

public:
	MyLinkedList() : dummyHead(new Node(0)), size(0) {}
	int get(int index) {
		if (index < 0 || index >= size)
			return -1;
		Node* cur = dummyHead->next;
		for (int i = 0; i < index; i++)
			cur = cur->next;
		return cur?cur->val:-1;
	}

	void addAtHead(int val) {
		Node* newNode = new Node(val);
		newNode->next = dummyHead->next;
		dummyHead->next = newNode;
		size++;
	}

	void addAtTail(int val) {
		Node* newNode = new Node(val);
		Node* cur = dummyHead;
		while (cur->next)
			cur = cur->next;
		cur->next = newNode;
		size++;
	}

	void addAtIndex(int index, int val) {
		if (index > size||index<0)
			return;
		Node* newNode = new Node(val);
		Node* cur = dummyHead;
		for (int x = 0; x < index; x++) {
			cur = cur->next;
		}
		newNode->next = cur->next;
		cur->next = newNode;
		size++;
	}

	void deleteAtIndex(int index) {
		if (index > size)
			return;
		Node* cur = dummyHead;
		while (index--) {
			cur = cur->next;
		}
		Node* toDelete = cur->next;
		cur->next = toDelete->next;
		delete toDelete;
		size--;
	}
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */


int main()
{
	MyLinkedList m;
	MyLinkedList* myLinkedList = new MyLinkedList();
	myLinkedList->deleteAtIndex(0);

	//myLinkedList->addAtHead(7);
	//myLinkedList->addAtHead(2);
	//myLinkedList->addAtHead(1);
	//myLinkedList->addAtIndex(3, 0);  

	//myLinkedList->deleteAtIndex(2);    
	//myLinkedList->addAtHead(6);
	//myLinkedList->addAtTail(4);
	//myLinkedList->get(4);
	//myLinkedList->addAtHead(4);

	//myLinkedList->addAtIndex(5, 0);
	//myLinkedList->addAtHead(6);
	//myLinkedList->get(1);              
	//myLinkedList->get(1);


	return 0;
}
